|
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices ''v'' and ''w'' at any distance ''i'', and any other two vertices ''x'' and ''y'' at the same distance, there is an automorphism of the graph that carries ''v'' to ''x'' and ''w'' to ''y''. A distance transitive graph is vertex transitive and symmetric as well as distance regular. A distance-transitive graph is interesting partly because it has a large automorphism group. Some interesting finite groups are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2. Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith, who showed that there are only 12 finite trivalent distance-transitive graphs. These are: |- | Petersen graph || 10 || 2 || 5 || |- | Graph of the cube || 8 || 3 || 4 || |- | Heawood graph || 14 || 3 || 6 || |- | Pappus graph || 18 || 4 || 6 || |- | Coxeter graph || 28 || 4 || 7 || |- | Tutte–Coxeter graph || 30 || 4 || 8 || |- | Graph of the dodecahedron || 20 || 5 || 5 || |- | Desargues graph || 20 || 5 || 6 || |- | Biggs-Smith graph || 102 || 7 || 9 || |- | Foster graph || 90 || 8 || 10 || |} Independently in 1969 a Russian group led by Georgy Adelson-Velsky showed that there exist graphs that are distance-regular but not distance-transitive. The only graph of this type with degree three is the 126-vertex Tutte 12-cage. The smallest distance-regular graph that is not distance-transitive is the Shrikhande graph. Complete lists of distance-transitive graphs are known for some degrees larger than three, but the classification of distance-transitive graphs with arbitrarily large vertex degree remains open. The simplest asymptotic family of examples of distance-transitive graphs is the Hypercube graphs. Other families are the folded cube graphs and the square rook's graphs. All three of these families have arbitrarily high degree. ==References== ;Early works *. *. *. *. *. ;Surveys *, chapter 20. *. *, chapter 7. *. *, section 4.5. *. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Distance-transitive graph」の詳細全文を読む スポンサード リンク
|